#include <stdlib.h>
#include <stdio.h>
#include"main.h"
void _recur_create_tree(BiTreeNode *root_p,char *pre_order_seq,int*current_index_p,int num_chars) {
	if (*current_index_p >= num_chars) {
		return;
	}
	root_p->data = pre_order_seq[*current_index_p];
	(*current_index_p)++;
	if (*current_index_p < num_chars) {
		if (pre_order_seq[*current_index_p] != '#') {
			root_p->leftChild = (BiTreeNode *) malloc(sizeof(BiTreeNode));
			_recur_create_tree(root_p->leftChild, pre_order_seq, current_index_p, num_chars);
		} else {
			root_p->leftChild = NULL;
			(*current_index_p)++;
		}
	} else {
		root_p->leftChild = NULL;
	}

	if (*current_index_p < num_chars) {
		if (pre_order_seq[*current_index_p] != '#') {
			root_p->rightChild = (BiTreeNode *) malloc(sizeof(BiTreeNode));
			_recur_create_tree(root_p->rightChild, pre_order_seq, current_index_p, num_chars);
		} else {
			root_p->rightChild = NULL;
			(*current_index_p)++;
		}
	} else {
		root_p->rightChild = NULL;
	}
}
void create_tree(BiTreeNode **root_pp,char*pre_order_seq,int num_elements){
	if(num_elements==0||pre_order_seq[0]=='#'){
		*root_pp=NULL;
		return;
	}
	int current_index=0;
	*root_pp=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	_recur_create_tree(*root_pp,pre_order_seq,&current_index,num_elements);
}
void destroy(BiTreeNode **root){
	if(*root==NULL){
		return;
	}
	destroy(&((*root)->leftChild));
	destroy(&((*root)->rightChild));
	free(*root);
	*root=NULL;
}
void pre_order_traverse(BiTreeNode *t,void visit(DataType item)){
	if(t==NULL){
		return;
	}
	visit(t->data);
	pre_order_traverse(t->leftChild,visit);
	pre_order_traverse(t->rightChild,visit);
}
void in_order_traverse(BiTreeNode *t,void visit(DataType item)){
	if(t==NULL){
		return;
	}
	in_order_traverse(t->leftChild,visit);
	visit(t->data);
	in_order_traverse(t->rightChild,visit);
}
void post_order_traverse(BiTreeNode *t,void visit(DataType item)){
	if(t==NULL){
		return ;
	}
	post_order_traverse(t->leftChild,visit);
	post_order_traverse(t->rightChild,visit);
	visit(t->data);
}
BiTreeNode *search(BiTreeNode *root,DataType x){
	if(root==NULL){
		return NULL;
	}
	if(root->data==x){
		return root;
	}
	BiTreeNode *left=search(root->leftChild,x);
	if(left !=NULL){
		return  left;
	}
	return search(root->rightChild,x);
}
void Visit(DataType item){
	printf("%c",item);
}
int main(void){
	BiTreeNode *root,*find;
	char *pre_order_seq="ABC##DE#G##F###";
	create_tree(&root,pre_order_seq,15);
	pre_order_traverse(root,Visit);
	printf("\n");
	in_order_traverse(root,Visit);
	printf("\n");
	post_order_traverse(root,Visit);
	char x='E';
	find =search(root,x);
	if(find!=NULL)
		printf("\nFound %c in the tree.\n",x);
	else
		printf("\n%c not found in the tree.\n",x);
	x='H';
	find =search(root,x);
	if(find !=NULL)
		printf("\nFound %c in the tree.\n",x);
	else
		printf("\n%c not found in the tree.\n",x);
	destroy(&root);
	return 0;
}